/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：LeftistHeap.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-07
Function List ：
Description   ：Leftist Heap
******************************************************/

#include "LeftistHeap.h"
#include <stdlib.h>   // for malloc
#include "FatalError.h"

struct TreeNode {
    ElementType   Element;
    PriorityQueue Left;
    PriorityQueue Right;
    int           Npl;
};

// Static Function Lists
static void SwapChildren(PriorityQueue H);
static PriorityQueue Merge1(PriorityQueue H1, PriorityQueue H2);

PriorityQueue Initialize(void) {
    return NULL;
}

PriorityQueue Destroy(PriorityQueue H) {
    if (H != NULL) {
        Destroy(H->Left);
        Destroy(H->Right);
        free(H);
    }

    return NULL;
}

ElementType FindMin(PriorityQueue H) {
    if (!IsEmpty(H)) {
        return H->Element;
    } else {
        Error("Priority Queue is empty");
        return 0;
    }
}

int IsEmpty(PriorityQueue H) {
    return H == NULL;
}

PriorityQueue Merge(PriorityQueue H1, PriorityQueue H2) {
    if (H1 == NULL) {
        return H2;
    }

    if (H2 == NULL) {
        return H1;
    }

    if (H1->Element < H2->Element) {
        return Merge1(H1, H2);
    } else {
        return Merge1(H2, H1);
    }
}

static void SwapChildren(PriorityQueue H) {
    PriorityQueue Tmp;

    Tmp = H->Left;
    H->Left = H->Right;
    H->Right = Tmp;
}

static PriorityQueue Merge1(PriorityQueue H1, PriorityQueue H2) {
    /* Single node */
    if (H1->Left == NULL) {
        /* H1->Right is already NULL, */
        /* H1->Npl is already 0 */
        H1->Left = H2;
    } else {
        H1->Right = Merge(H1->Right, H2);
        if (H1->Left->Npl < H1->Right->Npl) {
            SwapChildren(H1);
        }

        H1->Npl = H1->Right->Npl + 1;
    }

    return H1;
}

PriorityQueue Insert1(ElementType X, PriorityQueue H) {
    PriorityQueue SingleNode;

    SingleNode = (PriorityQueue)malloc(sizeof(struct TreeNode));
    if (SingleNode == NULL) {
        FatalError("Out of space!!!");
    } else {
        SingleNode->Element = X;
        SingleNode->Npl = 0;
        SingleNode->Left = NULL;
        SingleNode->Right = NULL;
        H = Merge(SingleNode, H);
    }

    return H;
}

/* DeleteMin1 returns the new tree; */
/* To get the minimum, use FindMin */
/* This is for convenience */
PriorityQueue DeleteMin1(PriorityQueue H) {
    PriorityQueue LeftHeap;
    PriorityQueue RightHeap;

    if (IsEmpty(H)) {
        Error("Priority queue is empty");
        return H;
    }

    LeftHeap = H->Left;
    RightHeap = H->Right;
    free(H);

    return Merge(LeftHeap, RightHeap);
}

Position Left(Position P) {
    return P->Left;
}

Position Right(Position P) {
    return P->Right;
}

ElementType Retrieve(Position P) {
    return P->Element;
}

// EOF

